package com.nan.leetcode.剑指offer第二版.从上到下打印二叉树;


import javax.xml.soap.Node;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }
public class Main {
    public int[] levelOrder1(TreeNode root) {
        if(root==null){
            return new int[0];
        }
        //创建一个队列来存放节点
        Queue<TreeNode> queue=new LinkedList<>();//队列是用链表来实现的
        //对于数组（数据结构），一旦被定义，其维数和维界就不再改变，从而其一般不作插入或者删除操作
        ArrayList<Integer> arrayList=new ArrayList<>();//存放值，不直接使用数组因为数组长度不可变，不能随意给数组里面增加元素
        queue.offer(root);//先将根节点放入队列中
        while (!queue.isEmpty()){
            TreeNode node=queue.poll();//队首元素出队
            //节点的值放入arralist
            arrayList.add(node.val);
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
        }
        int[] res=new int[arrayList.size()];
        //遍历ArrayList将数组放入数组中
        for(int i=0;i<arrayList.size();i++){
            res[i]= arrayList.get(i);
        }
        return res;
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        List<List<Integer>> res=new ArrayList<>();
        if(root==null){
            return res;
        }
        queue.offer(root);
        while (!queue.isEmpty()){
            List<Integer> tmp=new ArrayList<>();//新建一个临时列表 tmp ，用于存储当前层打印结果；
            for(int i= queue.size();i>0;i--){//循环让每一层的数据打印，for(int i= queue.size();i>0;i--)
                // 因为for循环在执行的过程中队列长度是会变化的，所以让i最开始先为队列长度，之后即使队列长度变换，
                // 也不影响i的值
                TreeNode node =queue.poll();
                tmp.add(node.val);
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
            res.add(tmp);//当前层遍历完，就把结果放入结果集里面。
        }
        return res;
    }
}
